package leetcode.Top100;

import java.util.HashMap;
import java.util.Map;

public class Top052_LC146 {
    class LRUCache {
        // 双向链表结点
        class Node<K, V> {
            int key;
            int value;
            Node<Integer, Integer> prev;
            Node<Integer, Integer> next;
            public Node () {
                this.prev = this.next = null;
            }
            public Node (int key, int value) {
                this.key = key;
                this.value = value;
                this.prev = this.next = null;
            }
        }

        // 双向链表
        class DoubleList {
            Node<Integer, Integer> head;
            Node<Integer, Integer> tail;
            public DoubleList() {
                head = new Node<Integer, Integer>();
                tail = new Node<Integer, Integer>();
                head.next = tail;
                tail.prev = head;
            }
            // 添加结点
            public void addHead(Node<Integer, Integer> node) {
                node.next = head.next;
                node.prev = head;
                head.next.prev = node;
                head.next = node;
            }
            // 移除结点
            public void removeNode(Node<Integer, Integer> node) {
                node.prev.next = node.next;
                node.next.prev = node.prev;
                node.next = null;
                node.prev = null;
            }
            // 获取头结点
            public Node<Integer, Integer> getHead() {
                return head.next;
            }
            // 获取尾节点
            public Node<Integer, Integer> getTail() {
                return tail.prev;
            }
        }

        private int capacity;
        Map<Integer, Node<Integer, Integer>> map;
        DoubleList doubleList;

        public LRUCache(int capacity) {
            this.capacity = capacity;
            map = new HashMap<>(capacity);
            doubleList = new DoubleList();
        }

        public int get(int key) {
            if (!map.containsKey(key)) {
                return -1;
            }
            Node<Integer, Integer> node = map.get(key);
            doubleList.removeNode(node);
            doubleList.addHead(node);
            return node.value;
        }

        public void put(int key, int value) {
            if (map.containsKey(key)) {
                Node<Integer, Integer> node = map.get(key);
                node.value = value;
                doubleList.removeNode(node);
                doubleList.addHead(node);
                map.put(key, node);
            } else {
                if (map.size() == capacity) {
                    Node<Integer, Integer> lastNode = doubleList.getTail();
                    doubleList.removeNode(lastNode);
                    map.remove(lastNode.key);
                }
                Node<Integer, Integer> newNode = new Node<Integer, Integer>(key, value);
                doubleList.addHead(newNode);
                map.put(key, newNode);
            }
        }
    }
}
